package com.linyaonan.leetcode.medium._73;

/**
 * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 *
 * 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出：[[1,0,1],[0,0,0],[1,0,1]]
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[0].length
 * 1 <= m, n <= 200
 * -2^31 <= matrix[i][j] <= 2^31 - 1
 *
 *
 * 进阶：
 *
 * 一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 * 你能想出一个仅使用常量空间的解决方案吗？
 *
 * @author: Lin
 * @date: 2024/9/23
 */
public class SetMatrixZeroes {

    /**
     * 使用辅助矩阵m x n记录原始零，然后对照该矩阵进行修改原矩阵
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        // 实现过程略
    }

    /**
     * 通过分析可以发现，如果 index = k,v 的原始数值为0，那么与其横向，纵向的数据会全部变为0
     * 上面k,v如果为0，那么只有不在k，v的横纵列才有记录的意义
     * int[] i 只用来记录横坐标
     * int[] j 只用来记录纵坐标
     *
     * 重新遍历原始数据时是需要查看横纵坐标是否在上面两个的覆盖范围就替换数值
     *
     * @param matrix
     */
    public void setZeroes2(int[][] matrix) {
        // 用来记录列有多少原始0
        int[] i = new int[matrix.length];
        // 用来记录行有多少原始0
        int[] j = new int[matrix[0].length];

        for (int i1 = 0; i1 < matrix.length; i1++) {
            for (int j1 = 0; j1 < matrix[i1].length; j1++) {
                if (matrix[i1][j1] == 0) {
                    i[i1] = 1;
                    j[j1] = 1;
                }
            }
        }

        for (int i1 = 0; i1 < matrix.length; i1++) {
            for (int j1 = 0; j1 < matrix[i1].length; j1++) {
                if (i[i1] == 1 || j[j1] == 1) {
                    matrix[i1][j1] = 0;
                }
            }
        }

    }

}
